package zuoshen_video2.dynamic;

import org.junit.Test;

public class CopeWipe {
    
    class Solution {
        public int cuttingRope(int n) {
            if (n == 2) return 1;
            p = new int[n + 1][100000];
            return dfs(n, 1);
        }

        int[][] p;
        public int dfs(int cur, int sum) {
            if (p[cur][sum] != 0) {
                System.out.println("I am used");
                return p[cur][sum];
            }
            if (cur == 0) return sum;
            int res = 0;
            for (int i = 1; i <= cur; i++) {
                res = Math.max(res, dfs(cur - i, sum * i));
            }
            p[cur][sum] = res;
            return res;
        }
    }

    @Test
    public void test1() {
        System.out.println(new Solution().cuttingRope(10));
    }


    class Solution2 {
        public int cuttingRope(int n) {
            if (n <= 3) return n - 1;
            int[] f = new int[n + 1];
            f[0] = 1;
            f[1] = 1;
            f[2] = 2;
            for (int i = 3; i <= n; i++) {
                f[i] = 0;
                for (int j = 1; j <= i; j++) { //切1个到不切(切i个就是不切)
                    f[i] = Math.max(f[i], f[i - j] * j);
                }
            }
            return f[n];
        }

        int[][] p;
        public int dfs(int cur, int sum) {
            if (p[cur][sum] != 0) {
                System.out.println("I am used");
                return p[cur][sum];
            }
            if (cur == 0) return sum;
            int res = 0;
            for (int i = 1; i <= cur; i++) {
                res = Math.max(res, dfs(cur - i, sum * i));
            }
            p[cur][sum] = res;
            return res;
        }
    }

    @Test
    public void test2() {
        System.out.println(new Solution2().cuttingRope(58));
    }

    //需要大数处理
    class Solution3 {
        public int cuttingRope(int n) {
            if (n <= 3) return n - 1;
            long[] f = new long[n + 1];
            f[0] = 1;
            f[1] = 1;
            f[2] = 2;
            for (int i = 3; i <= n; i++) {
                f[i] = 0;
                for (int j = 1; j <= i; j++) { //切1个到不切(切i个就是不切)
                    f[i] = Math.max(f[i], f[i - j] * j);
                }
            }
            return (int)f[n];
        }
    }
}
